package com.kznnc.data_structure.sort.one;

/**
 * @Description  希尔排序
 * @Author houchenkai
 * @Created Date: 2021/7/12 10:25
 * @ClassName
 */
public class ShellSortDemo {

    public static void main(String[] args) {
        int[] a = {6, 8, 9, 7, 2, 4, 1, 3, 5};
        int n = a.length;

        for (int add = n / 2; add >= 1; add /= 2) {
            // 外层是无序的数字 一个个将无序数字插入到有序序列
            for (int i = add; i < n; i++) {
                int data = a[i];
                int j = i - add;
                for (; j >= 0; j--) {
                    if (a[j] > data) {
                        a[j + add] = a[j];
                    } else {
                        break;
                    }
                }
                a[j + add] = data;
            }
        }

        for (int i : a) {
            System.out.println(i);
        }

    }
}
